package name.katlog.basic.sort;

import java.util.Arrays;


/**
 * @moudle: TestAlgSort 
 * @version:v1.0
 * @author: 丰伟
 * @date: 2017年12月25日 上午9:45:39
 *
 */
public class TestAlgSort {
	
	
	public static void quickSort(int[] arr){
	    qsort(arr, 0, arr.length-1);
	}
	private static void qsort(int[] arr, int low, int high){
	    if (low < high){
	        int pivot=partition(arr, low, high);        //将数组分为两部分
	        qsort(arr, low, pivot-1);                   //递归排序左子数组
	        qsort(arr, pivot+1, high);                  //递归排序右子数组
	    }
	}
	private static int partition(int[] arr, int low, int high){
	    int pivot = arr[low];     //枢轴记录
	    while (low<high){
	        while (low<high && arr[high]>=pivot) --high;
	        arr[low]=arr[high];             //交换比枢轴小的记录到左端
	        while (low<high && arr[low]<=pivot) ++low;
	        arr[high] = arr[low];           //交换比枢轴小的记录到右端
	    }
	    //扫描完成，枢轴到位
	    arr[low] = pivot;
	    //返回的是枢轴的位置
	    return low;
	}
	
	public static void main(String[] args) {
		int[] a = new int[]{6,5,9,4,2,7,8};
		quickSort(a);
		System.out.println(Arrays.toString(a));
	}
	
}
